{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Patching Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minPatches"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #按要求补齐数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个已排序的正整数数组 <code>nums</code>&nbsp;<em>，</em>和一个正整数&nbsp;<code>n</code><em> 。</em>从&nbsp;<code>[1, n]</code>&nbsp;区间内选取任意个数字补充到&nbsp;nums&nbsp;中，使得&nbsp;<code>[1, n]</code>&nbsp;区间内的任何数字都可以用&nbsp;nums&nbsp;中某几个数字的和来表示。</p>\n",
    "\n",
    "<p>请返回 <em>满足上述要求的最少需要补充的数字个数</em>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>nums = <code>[1,3]</code>, n = <code>6</code>\n",
    "<strong>输出: </strong>1 \n",
    "<strong>解释:</strong>\n",
    "根据 nums&nbsp;里现有的组合&nbsp;<code>[1], [3], [1,3]</code>，可以得出&nbsp;<code>1, 3, 4</code>。\n",
    "现在如果我们将&nbsp;<code>2</code>&nbsp;添加到&nbsp;nums 中，&nbsp;组合变为: <code>[1], [2], [3], [1,3], [2,3], [1,2,3]</code>。\n",
    "其和可以表示数字&nbsp;<code>1, 2, 3, 4, 5, 6</code>，能够覆盖&nbsp;<code>[1, 6]</code>&nbsp;区间里所有的数。\n",
    "所以我们最少需要添加一个数字。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>nums = <code>[1,5,10]</code>, n = <code>20</code>\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释: </strong>我们需要添加&nbsp;<code>[2,4]</code>。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>nums = <code>[1,2,2]</code>, n = <code>5</code>\n",
    "<strong>输出:</strong> 0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>nums</code>&nbsp;按 <strong>升序排列</strong></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 2<sup>31</sup>&nbsp;- 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [patching-array](https://leetcode.cn/problems/patching-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [patching-array](https://leetcode.cn/problems/patching-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3]\\n6', '[1,5,10]\\n20', '[1,2,2]\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        add, i,cunt = 1, 0, 0\n",
    "        while add <= n:\n",
    "            if i < len(nums) and nums[i] <= add:\n",
    "                add += nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                add += add\n",
    "                cunt += 1\n",
    "        return cunt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        mmax = 0\n",
    "        ret = 0\n",
    "        for v in nums:\n",
    "            if mmax >= n:\n",
    "                return ret\n",
    "            # print('element', v)\n",
    "            if mmax >= v-1:\n",
    "                mmax += v\n",
    "                # print('to', mmax)\n",
    "            else:\n",
    "                while mmax < v-1:\n",
    "                    ret += 1\n",
    "                    # print(mmax+1)\n",
    "                    mmax += mmax + 1\n",
    "                    # print('to', mmax)\n",
    "                    if mmax >= n:\n",
    "                        return ret\n",
    "                mmax += v\n",
    "        while mmax < n:\n",
    "            ret += 1\n",
    "            mmax += mmax + 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        a, b, ans = 1, 0, 0\n",
    "        for x in nums + [n]:\n",
    "            while b < min(x - 1, n):\n",
    "                b += a\n",
    "                a += a\n",
    "                ans += 1\n",
    "            b += x\n",
    "            a = b + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        rt, temp = 0, 1\n",
    "        # if nums[0] != 1:\n",
    "        #     rt += 1\n",
    "        idx = 0\n",
    "        ll = len(nums)\n",
    "        while temp <= n:\n",
    "            if idx < ll and nums[idx] <= temp:\n",
    "                temp += nums[idx]\n",
    "                idx += 1\n",
    "            else:\n",
    "                rt += 1\n",
    "                # temp *= 2\n",
    "                temp <<= 1\n",
    "        return rt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        x = 1\n",
    "        index = 0\n",
    "        size = len(nums)\n",
    "        count = 0\n",
    "        while x <= n:\n",
    "            if index < size and nums[index] <= x:\n",
    "                x += nums[index]\n",
    "                index += 1\n",
    "            else:\n",
    "                x *= 2\n",
    "                count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            while l < n and l + 1 - num < 0:\n",
    "                ans += 1\n",
    "                l += l + 1\n",
    "            l += num\n",
    "        while l < n:\n",
    "            ans += 1\n",
    "            l += l + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        sum = 0\n",
    "        now = 1\n",
    "        index = 0\n",
    "        while now <= n:\n",
    "            \n",
    "            if index < len(nums) and nums[index] <= now:\n",
    "                now += nums[index]\n",
    "                index += 1\n",
    "            else:\n",
    "                sum += 1\n",
    "                now *= 2\n",
    "\n",
    "        return sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        ret=0\n",
    "        x=1\n",
    "        l,i=len(nums),0\n",
    "        while x<=n:\n",
    "            if i<l and nums[i]<=x:\n",
    "                x+=nums[i]\n",
    "                i+=1\n",
    "            else:\n",
    "                x*=2\n",
    "                ret+=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        add, i,cunt = 1, 0, 0\n",
    "        while add <= n:\n",
    "            if i < len(nums) and nums[i] <= add:\n",
    "                add += nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                add += add\n",
    "                cunt += 1\n",
    "        return cunt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        length, index = len(nums), 0\n",
    "        patches, x = 0, 1\n",
    "        while x <= n:\n",
    "            if index < length and nums[index] <= x:\n",
    "                x += nums[index]\n",
    "                index += 1\n",
    "            else:\n",
    "                x <<= 1\n",
    "                patches += 1\n",
    "        return patches"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        maxi=0\n",
    "        cnt=0\n",
    "        nums+=[n+1]\n",
    "        for x in nums:\n",
    "            while maxi<x-1 and maxi<n:\n",
    "                #print(maxi+1)\n",
    "                maxi+=maxi+1\n",
    "                cnt+=1\n",
    "            maxi+=x\n",
    "            if maxi>=n:\n",
    "                return cnt\n",
    "        return \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        patches, x = 0, 1\n",
    "        length, index = len(nums), 0\n",
    "        while x <= n:\n",
    "            if index < length and nums[index] <= x:\n",
    "                x += nums[index]\n",
    "                index += 1\n",
    "            else:\n",
    "                x <<= 1\n",
    "                patches += 1\n",
    "        return patches\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def minPatches(nums, n):\n",
    "    patches = 0\n",
    "    covered = 0\n",
    "    i = 0\n",
    "    length = len(nums)\n",
    "\n",
    "    while covered < n:\n",
    "        if i < length and nums[i] <= covered + 1:\n",
    "            covered += nums[i]\n",
    "            i += 1\n",
    "        else:\n",
    "            covered += covered + 1\n",
    "            patches += 1\n",
    "\n",
    "    return patches\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        return minPatches(nums,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        res = 0\n",
    "        x = 1\n",
    "        index = 0\n",
    "        while x <= n:\n",
    "            if index < len(nums) and nums[index] <= x:\n",
    "                x += nums[index]\n",
    "                index += 1\n",
    "            else:\n",
    "                res += 1\n",
    "                x = x * 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        # 1 1 2 2  5 6 7\n",
    "        # 一个数在数组中  找到能不能被数组中元素求解出来 3 2 2 5 9\n",
    "        # 找到最小差距\n",
    "        x = 1\n",
    "        index = 0\n",
    "        addNumber = 0\n",
    "        addSum = 0\n",
    "        while x <= n:\n",
    "            if index < len(nums) and nums[index] <= x:\n",
    "                x += nums[index]\n",
    "                index += 1\n",
    "            else:\n",
    "                addNumber += 1\n",
    "                x *= 2\n",
    "        return addNumber\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        add, i, count = 1, 0, 0\n",
    "        while add <= n:\n",
    "            if i < len(nums) and nums[i] <= add:\n",
    "                add += nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                add += add\n",
    "                count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        length, x = len(nums), 1\n",
    "        ans = 0\n",
    "        \n",
    "        index = 0\n",
    "        \n",
    "        while x <= n:\n",
    "            if index < length and nums[index] <= x:\n",
    "                x += nums[index]\n",
    "                index += 1\n",
    "            else:\n",
    "                x <<= 1\n",
    "                ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        ans = mx = i = 0\n",
    "        L = len(nums)\n",
    "        while mx < n:\n",
    "            if i >= L or nums[i] > mx + 1:\n",
    "                ans += 1\n",
    "                # 要添加的数是mx + 1\n",
    "                mx += mx + 1\n",
    "            else:\n",
    "                mx += nums[i]\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        miss = 1\n",
    "        cur = 0\n",
    "        res = 0\n",
    "        while miss <= n:\n",
    "            if cur < len(nums) and nums[cur] <= miss:\n",
    "                miss += nums[cur]\n",
    "                cur += 1\n",
    "            else:\n",
    "                miss *= 2\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        ans = 1\n",
    "        curr = 0\n",
    "        i = 0\n",
    "        while ans <= n:\n",
    "            if i < len(nums) and nums[i] <= ans:\n",
    "                ans += nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                curr += 1\n",
    "                ans += ans\n",
    "        return curr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        m = len(nums)\n",
    "        cur_sum,count = 0,0\n",
    "        i = 0\n",
    "        while i < m:\n",
    "            while nums[i] > cur_sum+1:\n",
    "                cur_sum += cur_sum+1\n",
    "                count += 1\n",
    "                if cur_sum >= n:\n",
    "                    return count\n",
    "            cur_sum += nums[i]\n",
    "            i += 1\n",
    "            if cur_sum >= n:\n",
    "                    return count\n",
    "        while cur_sum < n:\n",
    "            cur_sum += cur_sum+1\n",
    "            count += 1\n",
    "        return count\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\r\n",
    "        min_sum_nums = 1\r\n",
    "        j, ans, length = 0, 0, len(nums)\r\n",
    "        while min_sum_nums<=n:\r\n",
    "            while j<length:\r\n",
    "                if nums[j]>min_sum_nums:\r\n",
    "                    break\r\n",
    "                min_sum_nums += nums[j]\r\n",
    "                j += 1\r\n",
    "            if min_sum_nums>n:\r\n",
    "                break\r\n",
    "            min_sum_nums += min_sum_nums\r\n",
    "            ans += 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        x = 1\n",
    "        idx = 0\n",
    "        res = 0\n",
    "        while x - 1 < n and idx < len(nums):\n",
    "            # print(x, idx)\n",
    "            if nums[idx] <= x:\n",
    "                x += nums[idx]\n",
    "                idx += 1\n",
    "            else:\n",
    "                res += 1\n",
    "                x *= 2\n",
    "            \n",
    "        print(res)\n",
    "        while x-1 < n:\n",
    "            res += 1\n",
    "            x *= 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        ans = mx = i = 0\n",
    "        L = len(nums)\n",
    "        \"\"\"\n",
    "        核心思想：\n",
    "        [1,12]都Ok \n",
    "        那么 + 10后，[1,22]都ok\n",
    "        \"\"\"\n",
    "        while mx < n:\n",
    "            if i >= L or nums[i] > mx + 1:\n",
    "                ans += 1\n",
    "                # 要添加的数是mx + 1\n",
    "                mx += mx + 1\n",
    "            else:\n",
    "                mx += nums[i]\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        ans = mx = i = 0\n",
    "        L = len(nums)\n",
    "        \"\"\"\n",
    "        核心思想：\n",
    "        [1,12]都Ok \n",
    "        那么nums[i]来了个10后，[1,22]都ok\n",
    "        但如果此时nums[i]只有14，那13这个就缺了，所以ans+1\n",
    "        \"\"\"\n",
    "        while mx < n:\n",
    "            if i >= L or nums[i] > mx + 1:\n",
    "                ans += 1\n",
    "                # 要添加的数是mx + 1\n",
    "                mx += mx + 1\n",
    "            else:\n",
    "                mx += nums[i]\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        target, i, count = 1, 0, 0\n",
    "        while target <= n:\n",
    "            if i < len(nums) and nums[i] <= target:\n",
    "                target += nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                target += target\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self,nums, n):\n",
    "        i=0\n",
    "        count=0\n",
    "        temp=1\n",
    "        while temp<=n:\n",
    "            if i<len(nums) and nums[i]<=temp:\n",
    "                temp+=nums[i]\n",
    "                i+=1\n",
    "                #print(n)\n",
    "            else:\n",
    "                temp += temp\n",
    "                count+=1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        count = 0\n",
    "        total = 0\n",
    "        idx = 0\n",
    "        while total < n:\n",
    "            if idx < len(nums) and nums[idx] <= total + 1:\n",
    "                total += nums[idx]\n",
    "                idx += 1\n",
    "            else:\n",
    "                total += total + 1\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        # count = 0\n",
    "        # while n > 0:\n",
    "        #     sum1 = n\n",
    "        #     nums1 = nums\n",
    "        #     nums1.sort()\n",
    "        #     for i in range(len(nums1)-1,-1,-1):\n",
    "        #         if sum1>=nums1[i]:\n",
    "        #             sum1 -= nums1[i]\n",
    "\n",
    "        #         if sum1 == 0:\n",
    "        #             n -= 1\n",
    "        #             break\n",
    "        #     if sum1!=0:\n",
    "        #         count += 1\n",
    "        #         nums1.append(sum1)\n",
    "\n",
    "        # return count\n",
    "        miss, i, added = 1, 0, 0\n",
    "        while miss <= n:\n",
    "            if i < len(nums) and nums[i] <= miss:\n",
    "                miss += nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                miss += miss\n",
    "                added += 1\n",
    "        return added\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        res = 0\n",
    "        x = 1\n",
    "        i = 0\n",
    "        while x<=n:\n",
    "            if i<len(nums) and nums[i]<=x:\n",
    "                x += nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                x <<=1\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        res = 0\n",
    "        x = 1\n",
    "        i = 0\n",
    "        while x<=n:\n",
    "            if i<len(nums) and nums[i]<=x:\n",
    "                x += nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                x *= 2\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        count = 0\n",
    "        # 能够覆盖的范围，我们的目标是覆盖[1, n]\n",
    "        total = 0\n",
    "        idx = 0\n",
    "        while total < n:\n",
    "            # e.g. [1,2,3] 遍历到3的时候，此时total = 6，即可以覆盖[1,6]的数字\n",
    "            if idx < len(nums) and nums[idx] <= total + 1:\n",
    "                total += nums[idx]\n",
    "                idx += 1\n",
    "            # e.g. 假设[1,2,3]下一个数字是 8，那么应该添加的数字是 total + 1 = 7\n",
    "            else:\n",
    "                total += total + 1\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        miss, i, added = 1, 0, 0\n",
    "        while miss <= n:\n",
    "            if i < len(nums) and nums[i] <= miss:\n",
    "                miss += nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                miss += miss\n",
    "                added += 1\n",
    "        return added\n",
    "        # count = 0\n",
    "        # while n > 0:\n",
    "        #     sum1 = n\n",
    "        #     nums1 = nums\n",
    "        #     nums1.sort()\n",
    "        #     for i in range(len(nums1)-1,-1,-1):\n",
    "        #         if sum1>=nums1[i]:\n",
    "        #             sum1 -= nums1[i]\n",
    "\n",
    "        #         if sum1 == 0:\n",
    "        #             n -= 1\n",
    "        #             break\n",
    "        #     if sum1!=0:\n",
    "        #         count += 1\n",
    "        #         n-=1\n",
    "        #         nums1.append(sum1)\n",
    "        # return count\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        m = len(nums)\n",
    "        res = 0\n",
    "        maxn = 1\n",
    "        i = 0\n",
    "\n",
    "        while maxn <= n:\n",
    "            if i < m and nums[i] <= maxn:\n",
    "                maxn += nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                maxn = maxn * 2\n",
    "                res += 1\n",
    "        \n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        x = 1 #表示[1,x-1]全覆盖,若x存在数组中，扩展至[1,2x-1]\n",
    "        count = 0\n",
    "        l = len(nums)\n",
    "        index = 0\n",
    "        while x <= n:  # 即覆盖最大值 x-1 < n时\n",
    "            if index < l and nums[index] <= x:\n",
    "                x += nums[index]\n",
    "                index += 1\n",
    "            else:\n",
    "                count += 1 #添加x,使得最大道2x-1\n",
    "                x <<= 1 #2倍\n",
    "        return count\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        ans = 0\n",
    "        x = 1\n",
    "        idx = 0\n",
    "        while x <= n:\n",
    "            if idx < len(nums) and nums[idx] <= x:\n",
    "                x += nums[idx]\n",
    "                idx += 1\n",
    "            else:\n",
    "                x *= 2\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        uncheck = 1\n",
    "        res = 0\n",
    "        ind = 0\n",
    "        while uncheck <= n:\n",
    "            if ind <= len(nums) - 1:\n",
    "                if nums[ind] > uncheck:\n",
    "                    res += 1\n",
    "                    uncheck = uncheck * 2\n",
    "                else:\n",
    "                    uncheck = nums[ind] + uncheck\n",
    "                    ind += 1\n",
    "            else:\n",
    "                res += 1\n",
    "                uncheck = uncheck * 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        edge, i, res = 1, 0, 0\n",
    "        while edge <= n:\n",
    "            if i < len(nums) and nums[i] <= edge:\n",
    "                edge += nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                edge += edge\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        add,i,count=1,0,0\n",
    "        while add<=n:\n",
    "            if i<len(nums) and nums[i]<=add:\n",
    "                add+=nums[i]\n",
    "                i+=1\n",
    "            else:\n",
    "                add+=add\n",
    "                count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        patches, x = 0, 1\n",
    "        length, index = len(nums), 0\n",
    "\n",
    "        while x <= n:\n",
    "            if index < length and nums[index] <= x:\n",
    "                x += nums[index]\n",
    "                index += 1\n",
    "            else:\n",
    "                x <<= 1\n",
    "                patches += 1\n",
    "        \n",
    "        return patches"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        add, i, count = 1, 0, 0\n",
    "        while add <= n:\n",
    "            if i < len(nums) and nums[i] <= add:\n",
    "                add += nums[i] # from [1, add] to [1, add + nums[i]]\n",
    "                i += 1\n",
    "            else:\n",
    "                add += add # from [1, add] to [1, 2add]\n",
    "                count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        ans = 0\n",
    "        cur_range = 0\n",
    "        next_n = 0\n",
    "        while cur_range < n:\n",
    "            if next_n >= len(nums) or nums[next_n] > cur_range + 1:\n",
    "                ans += 1\n",
    "                cur_range = cur_range * 2 + 1\n",
    "\n",
    "            elif nums[next_n] <= cur_range + 1:\n",
    "                next_n +=1\n",
    "                cur_range = cur_range + nums[next_n-1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        '''cnt,m=0,len(nums)\n",
    "        i,x=0,1\n",
    "        while x<=n:\n",
    "            if i<m and nums[i]<=x:\n",
    "                x+=nums[i]\n",
    "                i+=1\n",
    "            else:\n",
    "                cnt+=1\n",
    "                x<<=1\n",
    "        return cnt'''\n",
    "        maxi,ret=0,0\n",
    "        for num in nums:\n",
    "            while maxi<num-1:\n",
    "                maxi+=(maxi+1)\n",
    "                ret+=1\n",
    "                if maxi>=n:return ret #避免不必要添加数字\n",
    "            maxi+=num\n",
    "            if maxi>=n:return ret\n",
    "        while maxi<n:\n",
    "            maxi+=(maxi+1)\n",
    "            ret+=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        patches, x = 0, 1\n",
    "        length, index = len(nums), 0\n",
    "\n",
    "        while x <= n:\n",
    "            if index < length and nums[index] <= x:\n",
    "                x += nums[index]\n",
    "                index += 1\n",
    "            else:\n",
    "                x <<= 1\n",
    "                patches += 1\n",
    "        \n",
    "        return patches"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        nums.sort()\n",
    "        m = 0\n",
    "        res = 0\n",
    "        for c in nums:\n",
    "            if m >= n: break\n",
    "            while c > m + 1:\n",
    "                if m >= n: break\n",
    "                res += 1\n",
    "                m += m + 1\n",
    "            m += c \n",
    "        \n",
    "        while m < n:\n",
    "            res += 1\n",
    "            m += m + 1\n",
    "    \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        ans = 1\n",
    "        curr = 0\n",
    "        i = 0\n",
    "        while ans <= n:\n",
    "            if i < len(nums) and nums[i] <= ans:\n",
    "                ans += nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                curr += 1\n",
    "                ans += ans\n",
    "        return curr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        i,r,s=0,0,0\n",
    "        for nn in nums:\n",
    "            while s+1<min(n+1,nn):r,s=r+1,s+s+1\n",
    "            s+=nn\n",
    "            if s>=n:break\n",
    "        while s<n:r,s=r+1,s+s+1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        # count = 0\n",
    "        # while n > 0:\n",
    "        #     sum1 = n\n",
    "        #     nums1 = nums\n",
    "        #     nums1.sort()\n",
    "        #     for i in range(len(nums1)-1,-1,-1):\n",
    "        #         if sum1>=nums1[i]:\n",
    "        #             sum1 -= nums1[i]\n",
    "\n",
    "        #         if sum1 == 0:\n",
    "        #             n -= 1\n",
    "        #             break\n",
    "        #     if sum1!=0:\n",
    "        #         count += 1\n",
    "        #         nums1.append(sum1)\n",
    "\n",
    "        # return count\n",
    "        miss, i, added = 1, 0, 0\n",
    "        while miss <= n:\n",
    "            if i < len(nums) and nums[i] <= miss:\n",
    "                miss += nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                miss += miss\n",
    "                added += 1\n",
    "        return added\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        rt, temp = 0, 1\n",
    "        # if nums[0] != 1:\n",
    "        #     rt += 1\n",
    "        idx = 0\n",
    "        ll = len(nums)\n",
    "        while temp <= n:\n",
    "            if idx < ll and nums[idx] <= temp:\n",
    "                temp += nums[idx]\n",
    "                idx += 1\n",
    "            else:\n",
    "                rt += 1\n",
    "                temp *= 2\n",
    "        return rt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :param n:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        cnt = 0\n",
    "        idx = 0\n",
    "        len1 = len(nums)\n",
    "        start = 1\n",
    "        while start <= n:\n",
    "            if idx < len1 and nums[idx] <= start:\n",
    "                start += nums[idx]\n",
    "                idx += 1\n",
    "            else:\n",
    "                start *= 2\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n",
    "a = Solution()\n",
    "print(a.minPatches(nums = [1,2,2], n = 5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        nums.sort()\n",
    "        m = 0\n",
    "        res = 0\n",
    "        for c in nums:\n",
    "            while m < n and c > m + 1:\n",
    "                res += 1\n",
    "                m += m + 1\n",
    "            m += c \n",
    "        \n",
    "        while m < n:\n",
    "            res += 1\n",
    "            m += m + 1\n",
    "    \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(nums, n):\n",
    "    sum1 = 0  # 要插入数字的个数\n",
    "    bound = 0  # 可以表示的边界\n",
    "    while bound < n:\n",
    "        if nums and nums[0] == bound+1:\n",
    "            bound += nums[0]\n",
    "            nums.pop(0)\n",
    "            continue\n",
    "        if nums and nums[0] <= bound:\n",
    "            bound += nums[0]\n",
    "            nums.pop(0)\n",
    "            continue\n",
    "        sum1 += 1\n",
    "        bound += bound+1\n",
    "    return sum1\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        return func1(nums, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        pos=0\n",
    "        ins=0\n",
    "        res=0\n",
    "        while ins<n:\n",
    "            if pos==len(nums) or ins+1<nums[pos]:\n",
    "                res+=1\n",
    "                ins+=ins+1\n",
    "            else:\n",
    "                ins+=nums[pos]\n",
    "                pos+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        num = 1\n",
    "        index = 0\n",
    "        res = 0\n",
    "        while num <= n:\n",
    "            if index >= len(nums) or nums[index] > num:\n",
    "                num *= 2\n",
    "                res += 1\n",
    "            else:\n",
    "                num += nums[index]\n",
    "                index += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        ans = 0\n",
    "        x = 1\n",
    "        i = 0\n",
    "        while x <= n:\n",
    "            if i < len(nums) and nums[i] <= x:\n",
    "                x += nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                ans += 1\n",
    "                x *= 2\n",
    "        return ans\n",
    "            \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        patches, x = 0, 1\n",
    "\n",
    "        length, index = len(nums), 0\n",
    "\n",
    "\n",
    "        while x <= n:\n",
    "\n",
    "            if index < length and nums[index] <= x:\n",
    "\n",
    "                x += nums[index]\n",
    "                index += 1\n",
    "            else:\n",
    "\n",
    "                x <<= 1\n",
    "                #补充x\n",
    "                patches += 1\n",
    "        \n",
    "        return patches"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "        x, ans, i, ln = 1, 0, 0, len(nums)\n",
    "        while x <= n:\n",
    "            if i < ln and nums[i] <= x:\n",
    "                x += nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                x *= 2\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPatches(self, nums: List[int], n: int) -> int:\n",
    "\n",
    "        patches, x = 0, 1\n",
    "\n",
    "        length, index = len(nums), 0\n",
    "\n",
    "\n",
    "        while x <= n:\n",
    "\n",
    "            if index < length and nums[index] <= x:\n",
    "\n",
    "                x += nums[index]\n",
    "                index += 1\n",
    "            else:\n",
    "\n",
    "                x <<= 1\n",
    "                #补充x\n",
    "                patches += 1\n",
    "        \n",
    "        return patches"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
